struct ListNode
{
    ListNode(int value, ListNode* ptr = nullptr) {val = value; next = ptr;}
    int val;
    ListNode* next;
};

// 链表翻转
// first second third 三指针不断向后推，推到third为空则返回second
// 首先将头部处理，first->next置空，second->next=first，然后开始向后推
ListNode* reverseListNode(ListNode* first)
{
    if(!first || !first->next) // 链表非空且至少两个节点
        return first;
    ListNode* sec = first->next; // 定义second节点指针
    ListNode* third = sec->next; // 定义third节点指针
    first->next = nullptr; // 头节点next置空
    sec->next=first; // second->next=first
    while(third) // 开始向后推
    {
        first = sec; // 节点按照从左往右的顺序推，即头节点先推，third最后推
        sec = third;
        third = third->next;
        sec->next=first; // 三个节点先向后推一步，再改变前后指向
    }
    return sec; // third为空时结束翻转，sec是最后一个不为空节点，作为头节点返回
}


// 斐波拉西数列
// 递归
long fibonacci(long n)
{
    if(n<=0)
        return -1;
    if(n==1)
        return 0;
    if(n==2)
        return 1;
    return fibonacci(n-1)+fibonacci(n-2);
}
// 循环
long fibonacci(long n)
{
    if(n<=0)
        return -1;
    int first=0;
    int second=1;
    if(n==1)
        return first;
    if(n==2)
        return second;
    int temp=0;
    for(int i=3;i<=n;i++)
    {
        temp=second;
        second+=first;
        first=temp;
    }
    return second;
}

// 消除链表相邻项 12215 -> 5
// 三指针 s1 s2 s3 [s2-s3)为删除区间
ListNode* duplicate_removal(ListNode* head)
{
    if(!head || !head->next)
        return head;
    ListNode* s1=head, *s2=head, *s3=head->next;
    while(s3)
    {
        if(s3 && s3->val==s2->val) // 遇到相邻项
        {
            while(s3 && s3->val==s2->val) // s3向后推，直到空或者不相等
                s3=s3->next;
            if(s2==head) // 如果是头节点相邻节点相等，则更新头节点
            {
                head=s3;
                s1=head;
            }
            else
                s1->next=s3; // 将s1和删除后的链表接上
            s2=s3;
        }
        else
        {
            s1=s2; // s1和s2同一起点，s1先等于s2，s2再后推保证了s1在[s2,s3)之前
            s2=s2->next;
        }
        s3=s3->next; // s3向后推
    }
    return head;
}